package com.spirng.leetcode.day08;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Test216 {
    ArrayList arrayList=new ArrayList<List<Integer>>();
    LinkedList list=new LinkedList<Integer>();

    public static void main(String[] args) {
        String s="a";

        Test216 test216 = new Test216();
        test216.combinationSum3(3,7);

    }
    public List<List<Integer>> combinationSum3(int k, int n) {
         backtracking(k,n,1,0);
         return arrayList;
    }
    public void backtracking(int k, int n,int offSize,int sum) {
        if(sum>n){
            return;
        }
         if(sum==n&&list.size()==k){
             arrayList.add(new ArrayList<>(list));
             return;
         }
         if(list.size()==k){
             return;
         }
        for (int i = offSize; i <= 9; i++) {
             list.add(i);
             backtracking(k,n,i+1,sum+i);
             list.removeLast();
        }
    }
}
